package com.zhugang.week08;

import java.util.ArrayList;
import java.util.List;

/**
 * @program algorithms
 * @description: generateParenthesis
 * @author: chanzhugang
 * @create: 2022/08/20 19:00
 */
public class GenerateParenthesis {

    /**
     * 22 括号生成
     *
     * @param n
     * @return
     */
    private List<String> result = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        // 如n = 3， 生成3对括号，不同有效括号的组合， 穷举
        char[] path = new char[2 * n];
        backtrack(n, 0, 0, 0, path);
        return result;
    }

    /**
     * @param n
     * @param leftUsed
     * @param rightUsed
     * @param k
     * @param path
     */
    private void backtrack(int n, int leftUsed, int rightUsed, int k, char[] path) {
        // 括号成对出现，所以 2 * n
        if (k == 2 * n) {
            result.add(String.valueOf(path));
            return;
        }
        if (leftUsed < n) {
            // 有剩余的 '(' 都可以用'('
            path[k] = '(';
            backtrack(n, leftUsed + 1, rightUsed, k + 1, path);
        }
        if (leftUsed > rightUsed) {
            // 用过的'(' 比 ')'多才能用 ')'
            path[k] = ')';
            backtrack(n, leftUsed, rightUsed + 1, k + 1, path);
        }
    }

    public static void main(String[] args) {
        GenerateParenthesis generateParenthesis = new GenerateParenthesis();
        List<String> result = generateParenthesis.generateParenthesis(3);
        System.out.println(result.toString());
    }
}